Search Results

Documents authored by van Melkebeek, Dieter

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.29
Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols

Authors: Dieter van Melkebeek and Nicollas Mocelin Sdroievski

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Many derandomization results for probabilistic decision processes have been ported to the setting of Arthur-Merlin protocols. Whereas the ultimate goal in the first setting consists of efficient simulations on deterministic machines (BPP vs. P problem), in the second setting it is efficient simulations on nondeterministic machines (AM vs. NP problem). Two notable exceptions that have not yet been ported from the first to the second setting are the equivalence between whitebox derandomization and leakage resilience (Liu and Pass, 2023), and the equivalence between whitebox derandomization and targeted pseudorandom generators (Goldreich, 2011). We develop both equivalences for mild derandomizations of Arthur-Merlin protocols, i.e., simulations on Σ₂-machines. Our techniques also apply to natural simulation models that are intermediate between nondeterministic machines and Σ₂-machines.
Cite as

Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.FSTTCS.2023.29,
  author =	{van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas},
  title =	{{Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.29},
  URN =		{urn:nbn:de:0030-drops-194024},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.29},
  annote =	{Keywords: Hardness versus randomness tradeoff, leakage resilience, Arthur-Merlin protocol, targeted hitting set generator}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.17
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols

Authors: Dieter van Melkebeek and Nicollas Mocelin Sdroievski

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settings blackbox derandomization, i.e., derandomization through pseudo-random generators, has been shown equivalent to lower bounds for decision problems against circuits. Recently, Chen and Tell (FOCS'21) established near-equivalences in the BPP setting between whitebox derandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function f on the given instance. In this paper we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness to derandomization direction, consider a length-preserving function f computable by a nondeterministic algorithm that runs in time n^a. We show that if every Arthur-Merlin protocol that runs in time n^c for c = O(log² a) can only compute f correctly on finitely many inputs, then AM is in NP. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs for nondeterministic computations. As a byproduct of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). Byproducts in the average-case setting include the first uniform hardness vs. randomness tradeoffs for AM, as well as an unconditional mild derandomization result for AM.
Cite as

Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 17:1-17:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2023.17,
  author =	{van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas},
  title =	{{Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{17:1--17:36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.17},
  URN =		{urn:nbn:de:0030-drops-182870},
  doi =		{10.4230/LIPIcs.CCC.2023.17},
  annote =	{Keywords: Hardness versus randomness tradeoff, Arthur-Merlin protocol, targeted hitting set generator}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.119
Polynomial Identity Testing via Evaluation of Rational Functions

Authors: Dieter van Melkebeek and Andrew Morgan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. In spite of the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas. We study the power of the generator by characterizing its vanishing ideal, i.e., the set of polynomials that it fails to hit. Capitalizing on the univariate nature, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition size of set-multi-linearity in the vanishing ideal. Inspired by an alternating algebra representation, we develop a structured deterministic membership test for the vanishing ideal. As a proof of concept we rederive known derandomization results based on the generator by Shpilka and Volkovich, and present a new application for read-once oblivious arithmetic branching programs that provably transcends the usual combinatorial techniques.
Cite as

Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119,
  author =	{van Melkebeek, Dieter and Morgan, Andrew},
  title =	{{Polynomial Identity Testing via Evaluation of Rational Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{119:1--119:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119},
  URN =		{urn:nbn:de:0030-drops-157158},
  doi =		{10.4230/LIPIcs.ITCS.2022.119},
  annote =	{Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.20
Minimum Circuit Size, Graph Isomorphism, and Related Problems

Authors: Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
Cite as

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20,
  author =	{Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew},
  title =	{{Minimum Circuit Size, Graph Isomorphism, and Related Problems}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20},
  URN =		{urn:nbn:de:0030-drops-83455},
  doi =		{10.4230/LIPIcs.ITCS.2018.20},
  annote =	{Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.5
Derandomizing Isolation in Space-Bounded Settings

Authors: Dieter van Melkebeek and Gautam Prakriya

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance on shallow semi-unbounded circuits. A common approach employs small weight assignments that make the solution of minimum weight unique. The Isolation Lemma and other known procedures use Omega(n) random bits to generate weights of individual bitlength O(log(n)). We develop a derandomized version for both settings that uses O(log(n)^{3/2}) random bits and produces weights of bitlength O(log(n)^{3/2}) in logarithmic space. The construction allows us to show that every language in NL can be accepted by a nondeterministic machine that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input. Similarly, every language in LogCFL can be accepted by a nondeterministic machine equipped with a stack that does not count towards the space bound, that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input. We also show that the existence of somewhat more restricted isolations for reachability on digraphs implies that NL can be decided in logspace with polynomial advice. A similar result holds for certifying acceptance on shallow semi-unbounded circuits and LogCFL.
Cite as

Dieter van Melkebeek and Gautam Prakriya. Derandomizing Isolation in Space-Bounded Settings. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2017.5,
  author =	{van Melkebeek, Dieter and Prakriya, Gautam},
  title =	{{Derandomizing Isolation in Space-Bounded Settings}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{5:1--5:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.5},
  URN =		{urn:nbn:de:0030-drops-75297},
  doi =		{10.4230/LIPIcs.CCC.2017.5},
  annote =	{Keywords: Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification}
}
Document
DOI: 10.4230/DagRep.1.3.42
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)

Authors: Martin Grohe, Michal Koucky, Rüdiger Reischik, and Dieter van Melkebeek

Published in: Dagstuhl Reports, Volume 1, Issue 3 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11121 ``Computational Complexity of Discrete Problems''. The first section gives an overview of the topics covered and the organization of the meeting. Section~2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Martin Grohe, Michal Koucky, Rüdiger Reischik, and Dieter van Melkebeek. Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). In Dagstuhl Reports, Volume 1, Issue 3, pp. 42-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.1.3.42,
  author =	{Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)}},
  pages =	{42--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{3},
  editor =	{Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.3.42},
  URN =		{urn:nbn:de:0030-drops-31935},
  doi =		{10.4230/DagRep.1.3.42},
  annote =	{Keywords: Discrete problems, computational complexity, Turing machines, Boolean circuits, quantum computing, communication and query complexity, extractors, pseudorandomness, derandomization, approximation, coding cryptography, algorithmic learning}
}
Document
DOI: 10.4230/DagSemProc.09511.7
Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Authors: Holger Dell and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)

Abstract
Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer $d geq 3$ and positive real $epsilon$ we show that if satisfiability for $n$-variable $d$-CNF formulas has a protocol of cost $O(n^{d-epsilon})$ then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for $epsilon = 0$. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on $n$-vertex $d$-uniform hypergraphs, the above statement holds for any integer $d geq 2$. The case $d=2$ implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of $O(k^{2-epsilon})$ edges unless coNP is in NP/poly, where $k$ denotes the size of the deletion set. Kernels consisting of $O(k^2)$ edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.
Cite as

Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:DagSemProc.09511.7,
  author =	{Dell, Holger and van Melkebeek, Dieter},
  title =	{{Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses}},
  booktitle =	{Parameterized complexity and approximation algorithms},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9511},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.7},
  URN =		{urn:nbn:de:0030-drops-25043},
  doi =		{10.4230/DagSemProc.09511.7},
  annote =	{Keywords: Sparsification, Kernelization, Parameterized Complexity, Probabilistically Checkable Proofs, Satisfiability, Vertex Cover}
}
Document
DOI: 10.4230/DagSemProc.08381.1
08381 Abstracts Collection – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work as well as open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Abstracts Collection – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.1,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Abstracts Collection – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.1},
  URN =		{none},
  doi =		{10.4230/DagSemProc.08381.1},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.2
08381 Executive Summary – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.2,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Executive Summary – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.2},
  URN =		{urn:nbn:de:0030-drops-17789},
  doi =		{10.4230/DagSemProc.08381.2},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1363
Space Hierarchy Results for Randomized Models

Authors: Jeff Kinne and Dieter van Melkebeek

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following. Let $s(n)$ be any space-constructible function that is $Omega(log n)$ and such that $s(a n) = O(s(n))$ for all constants $a$, and let $s'(n)$ be any function that is $omega(s(n))$. - There exists a language computable by two-sided error randomized machines using $s'(n)$ space and one bit of advice that is not computable by two-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. - There exists a language computable by zero-sided error randomized machines in space $s'(n)$ with one bit of advice that is not computable by one-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. The condition that $s(a n)=O(s(n))$ is a technical condition satisfied by typical space bounds that are at most linear. We also obtain weaker results that apply to generic semantic models of computation.
Cite as

Jeff Kinne and Dieter van Melkebeek. Space Hierarchy Results for Randomized Models. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 433-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kinne_et_al:LIPIcs.STACS.2008.1363,
  author =	{Kinne, Jeff and van Melkebeek, Dieter},
  title =	{{Space Hierarchy Results for Randomized Models}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1363},
  URN =		{urn:nbn:de:0030-drops-13636},
  doi =		{10.4230/LIPIcs.STACS.2008.1363},
  annote =	{Keywords: Computations with Advice, Space Hierarchy, Randomized Machine, Promise Classes, Semantic Models}
}
Document
DOI: 10.4230/DagSemProc.06111.2
06111 Executive Summary – Complexity of Boolean Functions

Authors: Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of the Dagstuhl seminar "Complexity of Boolean Functions" held in March 2006, we introduce the different topics that have been discussed there and mention some of the major achievements. The summary closes with an outlook on the development of discrete computational complexity in the future.
Cite as

Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.2,
  author =	{Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger},
  title =	{{06111 Executive Summary – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2},
  URN =		{urn:nbn:de:0030-drops-8409},
  doi =		{10.4230/DagSemProc.06111.2},
  annote =	{Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning}
}
Document
DOI: 10.4230/DagSemProc.06111.1
06111 Abstracts Collection – Complexity of Boolean Functions

Authors: Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
From 12.03.06 to 17.03.06, the Dagstuhl Seminar 06111 ``Complexity of Boolean Functions'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.1,
  author =	{Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{06111 Abstracts Collection – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.1},
  URN =		{urn:nbn:de:0030-drops-7593},
  doi =		{10.4230/DagSemProc.06111.1},
  annote =	{Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization}
}
Document
DOI: 10.4230/DagSemProc.06111.3
A Generic Time Hierarchy for Semantic Models With One Bit of Advice

Authors: Dieter van Melkebeek and Konstantin Pervyshev

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We show that for any reasonable semantic model of computation and for any positive integer $a$ and rationals $1 leq c < d$, there exists a language computable in time $n^d$ with $a$ bits of advice but not in time $n^c$ with $a$ bits of advice. A semantic model is one for which there exists a computable enumeration that contains all machines in the model but may also contain others. We call such a model reasonable if it has an efficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic transducers. Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur-Merlin games of any signature, interactive proof protocols with one or multiple provers, etc.
Cite as

Dieter van Melkebeek and Konstantin Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:DagSemProc.06111.3,
  author =	{van Melkebeek, Dieter and Pervyshev, Konstantin},
  title =	{{A Generic Time Hierarchy for Semantic Models With One Bit of Advice}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.3},
  URN =		{urn:nbn:de:0030-drops-6151},
  doi =		{10.4230/DagSemProc.06111.3},
  annote =	{Keywords: Time hierarchy, non-uniformity, one bit of advice, probabilistic algorithms}
}
Document
DOI: 10.4230/DagSemProc.06111.20
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines

Authors: Scott Diehl and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
In this talk, we establish lower bounds for the running time of randomized machines with two-sided error which use a small amount of workspace to solve complete problems in the polynomial-time hierarchy. In particular, we show that for integers $l > 1$, a randomized machine with two-sided error using subpolynomial space requires time $n^{l - o(1)}$ to solve QSATl, where QSATl denotes the problem of deciding the validity of a Boolean first-order formula with at most $l-1$ quantifier alternations. This represents the first time-space lower bounds for complete problems in the polynomial-time hierarchy on randomized machines with two-sided error. Corresponding to $l = 1$, we show that a randomized machine with one-sided error using subpolynomial space requires time $n^{1.759}$ to decide the set of Boolean tautologies. As a corollary, this gives the same lower bound for satisfiability on deterministic machines, improving on the previously best known such result.
Cite as

Scott Diehl and Dieter van Melkebeek. Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{diehl_et_al:DagSemProc.06111.20,
  author =	{Diehl, Scott and van Melkebeek, Dieter},
  title =	{{Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--33},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.20},
  URN =		{urn:nbn:de:0030-drops-6054},
  doi =		{10.4230/DagSemProc.06111.20},
  annote =	{Keywords: Time-space lower bounds, lower bounds, randomness, polynomial-time hierarchy}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact